package com.study.algorithm.pathalgorithm.shortestpath;

import com.study.algorithm.datastruct.graph.GraphOperate;
import com.study.algorithm.datastruct.graph.impl.GraphOperateImpl;
import com.study.algorithm.datastruct.graph.model.Edge;
import com.study.algorithm.datastruct.graph.model.Graph;
import com.study.algorithm.datastruct.graph.model.Vertex;
import com.study.algorithm.utils.ListUtil;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 迪杰特斯拉最短路径寻找算法
 * 原理：为贪心算法的一种，每轮只取有利的结果（或者是路径最小）
 * <p>
 * 第一步：初始节点(A节点)单拎(含义：标记为已经访问)出来，其他节点排好队，轮番比较A到其它节点的距离（记distance（A，X）），
 * 取最小的距离的点记为B，则其距离为distance(A,B)
 * 第二步：将A，B单拎出来，其他节点继续排好队（记X)，轮番比较distance(A,X)和distance(A,B)+distance(B,X)
 * 取最小的距离的点记为C(distance(A,C)或者distance(A,B)+distance(B,C)是所有distance中最短的一个距离)
 * 第三步：重复步骤二，知道终点（目标结束点或者出口)被拎出来，结束
 */

public class Dijkstra {


    /**
     * 通过贪心算法实现最小路径计算（目前返回的是起点能到大的所有顶点的最短路径信息）
     *
     * @param graph
     * @param start 开始顶点
     * @param end   结束顶点（用来判断是否完成寻找目标)
     * @return 返回起点到目标结束顶点的最短路径和最短距离（目前返回的是所有的）
     */
    public Map<Vertex, Trace> getTheShortestPath(Graph graph, Vertex start, Vertex end) {

        GraphOperate operate = new GraphOperateImpl();
        Vertex startVertex = operate.containVertexAndReturnVertex(graph, start);
        Vertex endVertex = operate.containVertexAndReturnVertex(graph, end);

        if (graph == null || startVertex == null || endVertex == null) {
            return new HashMap<>(0);
        }


        Set<Vertex> endVertices = graph.getVertices()
                .stream().collect(Collectors.toSet());//排队比较节点集合。防止图中顶点集合被操作
        Map<Vertex, Trace> traceMap = new HashMap<>();//记录每个点最短距离路径
        Set<Vertex> visitedVertices = new HashSet<>();
        boolean nextVertextReachable = true;

        //把起始节点单拎出来
        visitedVertices.add(startVertex);
        endVertices.remove(startVertex);

        //放顶点在已经访问列表当中（顶点到自己的距离最短就是0
        putVertexToVisitedTraceMap(traceMap, startVertex, startVertex, 0);

//        while (!visitedVertices.contains(endVertex) && nextVertextReachable && !endVertices.isEmpty()) {
        while (nextVertextReachable && !endVertices.isEmpty()) {
            nextVertextReachable = findNextMiniDistanceVertex(operate, graph, traceMap, visitedVertices, endVertices);
        }
//        return visitedVertices.contains(endVertex) ? traceMap.get(endVertex) : null
        return traceMap;
    }

    /**
     * 使用贪心算法找到下一个距离起点最近距离的顶点
     *
     * @param operate
     * @param graph
     * @param traceMap        保存已经找到的最短路径顶点的路径
     * @param visitedVertices 已经找到最短路径的顶点集合
     * @param endVertices     还没有找到最短路径的顶点集合
     *                        （所以只能作为当前计算的结束顶点集合)
     * @return 如果返回不可达（false),父函数不会再尝试找下一个顶点（不会调用该函数）
     */

    public boolean findNextMiniDistanceVertex(GraphOperate operate, Graph graph, Map<Vertex, Trace> traceMap, Set<Vertex> visitedVertices, Set<Vertex> endVertices) {
        boolean reachable = true;

        Set<Edge> edges = operate.queryEdgesUsingStartVertiesAndEndVerties(graph, visitedVertices, endVertices);

        Iterator<Edge> it = edges.iterator();

        int currMiniDistance = Integer.MAX_VALUE;
        Vertex nextVisited = null;
        Vertex startVertex = null;
        while (it.hasNext()) {

            //变量记录，方便阅读
            Edge currEdge = it.next();
            Vertex currStartVertex = currEdge.getStartVetex();
            Vertex currEndVertex = currEdge.getEndVetex();
            Trace currTrace = traceMap.get(currStartVertex);
            int currDistance = computorDistance(currStartVertex, currTrace, currEdge);
            boolean isLower = currDistance != -1 && currDistance < currMiniDistance;

            //记录当前轮最小距离和路径
            if (isLower) {
                startVertex = currStartVertex;
                currMiniDistance = currDistance;
                nextVisited = currEndVertex;
            }
        }

        if (currMiniDistance == -1) {
            return !reachable;
        }
        putVertexToVisitedTraceMap(traceMap, startVertex, nextVisited, currMiniDistance);
        visitedVertices.add(nextVisited);
        endVertices.remove(nextVisited);
        return reachable;
    }


    public void putVertexToVisitedTraceMap(Map<Vertex, Trace> traceMap, Vertex startVertex, Vertex nextVisited, int distance) {
        Trace trace = traceMap.get(startVertex);
        Trace currTrace = new Trace();
        List<Vertex> traces = trace == null ? new LinkedList<>() : ListUtil.DeepClone(trace.getTraces());
        traces.add(nextVisited);
        currTrace.setTraces(traces);
        currTrace.setDistance(distance);
        traceMap.put(nextVisited, currTrace);
    }

    /**
     * 计算顶点通过该边到结束顶点的距离
     *
     * @param currStartVertex 当前边的开始节点，用来验证使用
     * @param trace           记录起点到每个已经扫描点的最短距离路径
     * @param edge            当前边（用来记录到下一个点的距离)
     * @return 如果距离不是无穷大（距离为空） 则返回距离，否则返回不可达（用-1表示)
     */
    public int computorDistance(Vertex currStartVertex, Trace trace, Edge edge) {
        int unreachable = -1;
        if (!currStartVertex.getVertex().equals(edge.getStartVetex().getVertex())) {
            return unreachable;
        }

        Integer distance = edge.getDistance();
        if (distance == null) {
            return unreachable;
        }
        return trace.getDistance() + distance;
    }


}
